COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a01.tex[162,phy] \today\hfill}

\line{Handout \#\ 3\hfill CS 144B Homework Assignment 1}
\line{\hfill Due: Friday, January 22, 1984}

\parindent 0pt
\smallskip
1.\xskip Train scheduling:

\smallskip
\display 30pt:a.:You are given a set $R$ of reservations. Each reservation
$r$ consists of a pair of integers $r↓i$, $r↓j$ (with $r↓i<r↓j$). 
$r↓i$~indicates where the passenger will board the train; $r↓j$ indicates where
the passenger will get off. The problem is to compute the minimum number of
seats required to accomodate all the passengers. Explain how this can be 
done in $O(n\log n)$ operations, where $n$ is the number of reservations.

\smallskip
\display 30pt:b.:Now assume that there are only $m$ railroad stations.
Thus for all reservations~$r$, $0<r↓i<r↓j≤m$. Explain how to compute the
minimum seat requirement in $O(m+n)$ operations.

\smallskip
2.\xskip The following algorithm is supposed to determine whether a list
of $n$~records is `topologically sorted'. Assume that the subroutine~$P$
implements a partial order relation $\ast$ on the records:
$$\eqalign{P(i,j)=&\hbox{``}=\hbox{'' if record $i=$ record $j$}\cr
&\hbox{``}<\hbox{'' if record $i\;\ast$ record $j$}\cr
&\hbox{``}>\hbox{'' if record $j\;\ast$ record $i$}\cr
&\hbox{``}{\textstyle\bigotimes}\hbox{'' if record $i$ is not related to 
record $j$}\cr}$$

\smallskip
\display 30pt:1.:\qquad $\hbox{\it ok\/} := \hbox{\bf true}$;
\display 30pt:2.:\qquad $i:=n-1$;
\display 30pt:3.:\qquad {\bf while} $i>0$ {\bf and} {\it ok} do
\display 30pt:4.:\qquad\quad {\bf begin}
\display 30pt:5.:\qquad\quad $j:=i+1$;
\display 30pt:6.:\qquad\quad ${\it unrelated\/}:={\bf true}$;
\display 30pt:7.:\qquad\quad {\bf while} $j≤n$ {\bf and} {\it unrelated\/} 
{\bf do}
\display 30pt:8.:\qquad\qquad {\bf case} $P(i,j)$ {\bf of}
\display 30pt:9.:\qquad\qquad\qquad ``$<$'', ``$=$'' : {\it unrelated\/} $:=$
{\bf false}:
\display 30pt:10.:\qquad\qquad\qquad ``$>$'' : {\bf begin} {\it ok\/}
$:=$ {\bf false}: {\it unrelated\/} $:=$ {\bf false end};
\display 30pt:11.:\qquad\qquad\qquad ``$\bigotimes$'': $j:=j+1$
\display 30pt:12.:\qquad\qquad {\bf end};
\display 30pt:13.:\qquad\quad $i:=i-1$;
\display 30pt:14.:\qquad\quad {\bf end};

\smallskip
\display 30pt:a.:Prove that this algorithm terminates with {\it ok\/} $=$
{\bf true} if the records are topologically sorted; {\bf false} otherwise.
(If the algorithm is not correct, demonstrate that, and find a way to fix it.)

\smallskip
\display 30pt:b.:How many calls to $P$ are made in the worst case?

\smallskip
\display 30pt:c.:Is it possible to improve this worst case behavior?
(If so do so, if not prove that you can't.)

3.\xskip Permutations:

\smallskip
\display 30pt:a.:Suppose that $S$ is a finite set and that $p\colon S→S$.
(That means that $p$ is a function from elements of $S$ to elements
of~$S$.) Prove that $p$ is one to one if and only if $p$ is onto. 
(Recall that a function~$p$ is called {\it one to one\/} provided that
$a≠b$ implies $f(a)≠f(b)$. $p$~is said to be {\it onto\/}~$S$ provided
that for every $s\in S$ there is an $r$ so that $f(r)=s$.)

\display 30pt:b.:Let $p$ be a permutation on the set $S$. (That is,
$p\colon S→S$ and $p$ is one to one and onto.) Show that $p$ has a
unique right inverse~$h$. (A function~$h$ is a right inverse of~$p$
if $p\bigl(h(i)\bigr)=i$ for all $i\in S$.) Also show that $p$ has
a unique left inverse $g$ (a~function $g$ such that
$g\bigl(p(i)\bigr)=i$ for all $i\in S$) and that $g=h$.

4.\xskip Let $d$ be a probability distribution. Prove that 
$V(d)=M↓2(d)-\bigl(M↓1(d)\bigr)↑2$. Recall the definitions:

\halign{\qquad\qquad\lft{#}\cr
Mean: $M↓1(d)=\Sigma↓iid(i)$\cr
\noalign{\vskip 2pt}
Second Moment: $M↓2(d)=\Sigma↓ii↑2d(i)$\cr
\noalign{\vskip 2pt}
Variance: $V(d)=\Sigma↓i\bigl(i-M↓1(d)\bigr)↑2d(i)$\cr}

\vfill\eject\end